package year2022.leetcode.simple;

import java.math.BigInteger;

public class Palindrome {

    public static void main(String[] args){
//[1,2,2,1]
        ListNode head = new ListNode(1);
        ListNode curr = head;
        ListNode next = new ListNode(2);

        curr.next = next;
        curr = next;

        next = new ListNode(3);
        curr.next = next;
        curr = next;

        next = new ListNode(4);
        curr.next = next;
        curr = next;

        next = new ListNode(3);
        curr.next = next;
        curr = next;

        next = new ListNode(2);
        curr.next = next;
        curr = next;

        next = new ListNode(1);
        curr.next = next;
        curr = next;

        Palindrome p = new Palindrome();

        System.out.println(p.isPalindrome(head));
    }

    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode curr = head;
        while (curr!=null){
            len++;
            curr = curr.next;
        }

        int l = len>>1;
        int[] part = new int[l];
        int p = 0;

        curr = head;

        while (l>0){
            part[p++] = curr.val;
            curr = curr.next;
            l--;
        }

        if ((len&1)==1){
            curr = curr.next;
        }

        while (curr!=null){
            if (part[--p] != curr.val){
                return false;
            }
            curr = curr.next;
        }

        return true;
    }

    public boolean isPalindrome2(ListNode head) {
        StringBuilder s = new StringBuilder();
        while (head!=null){
            s.append(head.val);
            head = head.next;
        }

        int len = s.length();
        int l = len-1;

        for (int i=0; i<len; i++){
            if (s.charAt(i)!=s.charAt(l-i)){
                return false;
            }
        }

        return true;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
